{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最小生成树MST\n",
    "\n",
    "\n",
    "一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。\n",
    "\n",
    "也就是说，用原图中有的边，连接n个节点，保证每个节点都被连接，且使用的边的数目最少。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最小权重生成树\n",
    "\n",
    "\n",
    "在一给定的无向图$G = (V, E) $中，$(u, v) $代表连接顶点$ u $与顶点 $v $的边（即），而 $w(u, v) $代表此边的权重，若存在 $T $为$ E $的子集（即）且为无循环图，使得\n",
    "\n",
    "$$w(t)=\\sum_{(u,v)\\in t}w(u,v)$$\n",
    "\n",
    "的$ w(T) $最小，则此 $T$ 为 $G$ 的最小生成树。\n",
    " \n",
    "最小生成树其实是最小权重生成树的简称。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 应用：\n",
    "\n",
    "\n",
    "例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。\n",
    "\n",
    "这就需要找到带权的最小生成树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prim算法\n",
    "\n",
    "\n",
    "1)、输入：一个加权连通图，其中顶点集合为$V$，边集合为$E$；\n",
    "\n",
    "2)、初始化：$V_{new}= \\{x\\}$，其中$x$为集合$V$中的任一节点（起始点），$E_{new}= \\{\\}$,为空；\n",
    "\n",
    "3)、重复下列操作，直到$V_{new}= V$：\n",
    "\n",
    " - a.在集合$E$中选取权值最小的边$<u, v>$，其中$u$为集合$V_{new}$中的元素，而$v$不在$V_{new}$集合当中，并且$v∈V$（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；\n",
    "   \n",
    " -  b.将$v$加入集合$V_{new}$中，将$<u, v>$边加入集合$E_{new}$中；\n",
    "\n",
    "4)、输出：使用集合$V_{new}$和$E_{new}$来描述所得到的最小生成树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Kruskal算法简述\n",
    "\n",
    "假设 $W_N=(V,{E}) $是一个含有n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：\n",
    "\n",
    "先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。\n",
    "\n",
    "之后，从网的边集 $E$ 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；\n",
    "\n",
    "反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。\n",
    "\n",
    "依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。\n",
    "\n",
    "循环中可加入已加入MST的点的数量的判断，有可能提前结束循环，提高效率。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面是hdu1233的源代码，一个用Prim算法，另一个用Kruskal，标准的MST问题。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <cstdio.h>\n",
    "#include <algorithm>\n",
    "using namespace std;\n",
    "\n",
    "typedef int weight_t; \n",
    "\n",
    "#define SIZE 101\n",
    "\n",
    "int N;\n",
    "\n",
    "//图的邻接矩阵\n",
    "weight_t Graph[SIZE][SIZE];\n",
    "\n",
    "//各顶点到中间结果的最短距离，始终维护\n",
    "weight_t D[SIZE];\n",
    "\n",
    "//标志位\n",
    "bool Flag[SIZE];\n",
    "\n",
    "//Prim算法，返回MST的长度\n",
    "weight_t Prim(){\n",
    "\t//初始化数组\n",
    "\tfill(D,D+SIZE,INT_MAX);\n",
    "\tfill(Flag,Flag+SIZE,false);\n",
    "\n",
    "\t//初始化第一个计算的点\n",
    "\tD[1] = 0;\n",
    "\n",
    "\tweight_t ans = 0;\n",
    "\n",
    "\tfor(int i=1;i<=N;++i){\n",
    "\t\t//找出距离中间结果最近的点\n",
    "\t\tint k = -1;\n",
    "\t\tfor(int j=1;j<=N;++j)\n",
    "\t\t\tif ( !Flag[j] && ( -1 == k || D[j] < D[k] ) )\n",
    "\t\t\t\tk = j;\n",
    "\n",
    "\t\t//将k点加入中间结果\n",
    "\t\tFlag[k] = true;\n",
    "\t\tans += D[k];\n",
    "\n",
    "\t\t//更新剩余点到中间结果的最短距离\n",
    "\t\tfor(int j=1;j<=N;++j)\n",
    "\t\t\tif ( !Flag[j] && Graph[k][j] < D[j] )\n",
    "\t\t\t\tD[j] = Graph[k][j];\n",
    "\t}\n",
    "\n",
    "\treturn ans;\n",
    "}\n",
    "\n",
    "bool read(){\n",
    "\tscanf(\"%d\",&N);\n",
    "\tif ( 0 == N ) return false;\n",
    "\t\n",
    "\tfor(int i=0;i<N*(N-1)/2;++i){\n",
    "\t\tint a,b,w;\n",
    "\t\tscanf(\"%d%d%d\",&a,&b,&w);\n",
    "\t\tGraph[a][b] = Graph[b][a] = w;\n",
    "\t}\n",
    "\t\n",
    "\treturn true;\n",
    "}\n",
    "\n",
    "int main(){\n",
    "\twhile( read() ){\n",
    "\t\tprintf(\"%d\\n\",Prim());\n",
    "\t}\n",
    "\treturn 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <cstdio>\n",
    "#include <algorithm>\n",
    "using namespace std;\n",
    "\n",
    "typedef int weight_t; \n",
    "\n",
    "#define SIZE 101\n",
    "\n",
    "//并查集结构\n",
    "int Father[SIZE];\n",
    "void init(int n){for(int i=0;i<=n;Father[i]=i++);}\n",
    "int find(int x){return Father[x]==x?x:Father[x]=find(Father[x]);}\n",
    "void unite(int x,int y){Father[find(y)]=Father[find(x)];}\n",
    "\n",
    "int N;\n",
    "\n",
    "//边结构\n",
    "struct edge_t{\n",
    "\tint s;\n",
    "\tint e;\n",
    "\tweight_t w;\n",
    "}Edge[SIZE*SIZE/2];\n",
    "int ECnt = 0;\n",
    "\n",
    "//重载，用于边排序\n",
    "bool operator < (edge_t const&lhs,edge_t const&rhs){\n",
    "\tif ( lhs.w != rhs.w ) return lhs.w < rhs.w;\n",
    "\tif ( lhs.s != rhs.s ) return lhs.s < rhs.s;\n",
    "\treturn lhs.e < rhs.e;\n",
    "}\n",
    "\n",
    "//生成边\n",
    "inline void mkEdge(int a,int b,weight_t w){\n",
    "\tif ( a > b ) swap(a,b);\n",
    "\n",
    "\tEdge[ECnt].s = a;\n",
    "\tEdge[ECnt].e = b;\n",
    "\tEdge[ECnt++].w = w;\n",
    "}\n",
    "\n",
    "//Kruskal算法，vn是点的数量，en是边的数量，返回MST的长度\n",
    "weight_t Kruskal(int vn,int en){\n",
    "\tinit(vn);//并查集初始化\n",
    "\tsort(Edge,Edge+en);//边排序\n",
    "\n",
    "\tweight_t ans = 0;\n",
    "\tfor(int i=0;i<en;++i){\n",
    "\t\t//该边已存在于MST中\n",
    "\t\tif ( find(Edge[i].s) == find(Edge[i].e) )\n",
    "\t\t\tcontinue;\n",
    "\n",
    "\t\t//将该边加入MST\n",
    "\t\tans += Edge[i].w;\n",
    "\t\tunite(Edge[i].s,Edge[i].e);\n",
    "\t\t--vn;\n",
    "\n",
    "\t\t//MST已完全生成\n",
    "\t\tif ( 1 == vn ) break;\n",
    "\t}\n",
    "\n",
    "\treturn ans;\n",
    "}\n",
    "\n",
    "bool read(){\n",
    "\tscanf(\"%d\",&N);\n",
    "\tif ( 0 == N ) return false;\n",
    "\t\n",
    "\tECnt = 0;\n",
    "\tfor(int i=0;i<N*(N-1)/2;++i){\n",
    "\t\tint a,b,w;\n",
    "\t\tscanf(\"%d%d%d\",&a,&b,&w);\n",
    "\t\tmkEdge(a,b,w);\n",
    "\t}\n",
    "\t\n",
    "\treturn true;\n",
    "}\n",
    "\n",
    "int main(){\n",
    "\twhile( read() ){\n",
    "\t\tprintf(\"%d\\n\",Kruskal(N,ECnt));\n",
    "\t}\n",
    "\treturn 0;\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "c"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
